package leetcode_300;

import java.util.ArrayList;
import java.util.List;

import helpclass.TreeNode;

/**
 *@author 周杨
 *LowestCommonAncestorOfABinarySearchTree_235 求二叉搜索树 两个节点的最近祖宗
 *describe:用递归 利用BST的特性 AC 100%
 *2018年6月24日 下午5:20:49
 */
public class LowestCommonAncestorOfABinarySearchTree_235 {
	/**
	 * describe:保存路径 只AC 4%
	 * 2018年6月24日 下午5:21:55
	 */
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP=path(p,root);
        List<TreeNode> pathQ=path(q,root);
        int indexP=pathP.size()-1;
        int indexQ=pathQ.size()-1;
        if(indexP>indexQ) {
        	indexP=indexQ;
        }
        else if(indexP<indexQ)
        	indexQ=indexP;
        while(indexP>=0) {
        	if(pathP.get(indexP).val==pathQ.get(indexP).val)
        		return pathP.get(indexP);
        	--indexP;
        }
        return null;
        
    }
	
	/**
	 * describe:递归算法 用BST的性质 祖宗一定是root往下走 每次都只选择一颗子树 慢慢裁剪
	 *  保证每次的root 都是祖先 (可能不是结果的祖先) 
	 * 2018年6月24日 下午5:22:18
	 */
	public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode tempRoot = root;
        while (tempRoot != null) {
            if (tempRoot == p || tempRoot == q) return tempRoot;
            if (tempRoot.val < p.val && tempRoot.val < q.val) tempRoot = tempRoot.right;
            if (tempRoot.val >= p.val && tempRoot.val >= q.val) tempRoot = tempRoot.left;
            else return tempRoot;
        }
        
        return tempRoot;
    }
	
	public List<TreeNode> path(TreeNode p,TreeNode root){
		List<TreeNode> res=new ArrayList<TreeNode>();
		TreeNode run=root;
		while(run.val!=p.val) {
			res.add(run);
			if(run.val>p.val)
				run=run.left;
			else
				run=run.right;
		}
		res.add(run);
		return res;
	}
}
